package prac6;

/**
 * Implementation of the Set interface for sets stored as a Linked List
 * 
 * @author			Menghong Li
 * @author			Ian Moriarty
 * @since			August 2011
 * @invariant		No elements appear twice in the set
 * @input			none
 * @output			Testing only
 * @errorHandling	none
 * @knownBugs		none
 */
public class LinkedSet<T> implements Set<T> {
	
	protected LinkedList<T> theSet;
		
    /**
     * Implements a set iterator.
     * 
     * @author			Menghong Li
     * @author			Ian Moriarty
     * @since			August 2011
     * @invariant		(1) current points to either a node in the list or to null
     * 					(2) if there exists a node in the list such that node.successor = current
     * 						then previous points to that node. Otherwise it is null.
     * @input			none
     * @output			none
     * @errorHandling	none
     * @knownBugs		none
     */
    protected class MyIterator implements Iterator<T> {
    	Iterator<T> i;
    	
    	/**
    	 * @complexity	Best and worst case: O(1)
    	 */
        protected MyIterator() {
        	i = theSet.iterator();
        }

        /**
         * Checks whether there is a subsequent element in the list
         * 
         * @return		Whether or not there is a subsequent element
         * @complexity	Best and worst case: O(1)
         */
        public boolean hasNext() {
            return i.hasNext();
        }
        
        /**
         * Returns the iterator to the start of the list
         * 
         * @post		The iterator is at the start of the list
         * @complexity	Best and worst case: O(1)
         */
        public void reset() {
        	i.reset();

        }
        
        /**
         * Peeks at the current element of the list
         * 
         * @return		The current element of the list
         * @complexity	Best and worst case: O(1)
         */
        public T peek() {
        	return i.peek();
        }

        /**
         * Iterate to the next element of the list and return it
         * 
         * @return		The next element in the list
         * @post		The iterator is at the next element of the list
         * @complexity	Best and worst case: O(1)
         */
        public T next() {
            return i.next();
        }

        /**
         * Deletes the current element of the list
         * 
         * @post		If there is an element that has not yet been iterated over, it deletes
         * 				it and moves over it. Otherwise it throws NoSuchMethodException.
		 * @post		Contains exactly the same elements as before, except for the element
		 * 				that was about to be iterated over.
         * @complexity	Best and worst case: O(1)
         */
        public void deleteHere() { 
        	i.deleteHere();
        }        
    }

    /**
     * Called by descendant classed to initialise the common instance variables.
     *
     * @post        the variables are set as for an  empty set object
     * @complexity  best and worst case: O(1) 
     */
    public LinkedSet() {
    	theSet = new UnsortedLinkedList<T>();
    }

    /**
	 * Checks if the set is empty
	 * 
	 * @return		Whether the set is empty
	 * @complexity	Best and worst case: O(1)
	 */
	@Override
	public boolean isEmpty() {
		return theSet.isEmpty();
	}

	/**
	 * Empties the set
	 * 
	 * @post		the set is empty
	 * @complexity	Best and worst case: O(1)
	 */
	@Override
	public void clear() {
		theSet.clear();
	}

	/**
	 * Checks whether item is a member of the set
	 * 
	 * @param		item
	 * @return		Whether item is a member of the set
	 * @complexity	Best case: O(M) - item is the first member of the set
	 * 				Worst case: O(N*M) - item is not a member of the set
	 * 				where	M is the complexity of comparing item and a member of the set
	 * 						N is the number of items in the set.
	 */
	@Override
	public boolean isMember(T thisItem) {
	   return theSet.find(thisItem);
	}

	/**
	 * Checks whether item is a member of the set and deletes it if found
	 * 
	 * @param		thisItem the item to be deleted
	 * @return		Whether an instance of thisItem was deleted
	 * @post		Contains exactly the same elements as before, except for thisItem which has been deleted
	 * @complexity	Best case: O(M) - item is the first member of the set
	 * 				Worst case: O(N*M) - item is not a member of the set
	 * 				where	M is the complexity of deleting item and a member of the set
	 * 						N is the number of items in the set.
	 */
	@Override
	public boolean deleteItem(T thisItem) {
		return theSet.deleteItem(thisItem);

	}

	/**
	 * Finds the size of the set
	 * 
	 * @return		The size of the set
	 * @complexity	Best and worst case: O(1)
	 */
	@Override
	public int cardinality() {
		return theSet.size();
	}

    /**
     * Add a new item to this list.
     * 
     * @param       newItem to add to this list
	 * @complexity	Best case: O(M) - item is already contained in the set as the first member
	 * 				Worst case: O(M*N) - item is not already contained in the set
	 * 				where	M is the complexity of adding item into the set
	 * 						N is the number of items in the set.
     * @post        the item will appear in the list. Where? it will depend on
     *              the particular concrete class
     */
	@Override
	public void add(T newItem){
		if(!theSet.find(newItem)) {
			theSet.add(newItem);
		}
	}

	/**
	 * Finds the intersection of this set and otherSet
	 * 
	 * @param		otherSet the set we're finding the intersection of this set with
	 * @return		The intersection set
	 * @complexity	Best case: O(M) - The sets are the same
	 * 				Worst case: O(M + N1*(N2*C)*(D*N)) - The sets are the same except for one element
	 * 				where	N1 is the size of this set
	 * 						N2 is the size of the other set
	 * 						N is the number of shared elements between N1 and N2
	 * 						C is the complexity of comparing two elements of the sets
	 * 						D is the complexity of adding an element to the intersection set
	 * 						M is the complexity of equals()
	 */
	@Override
	public LinkedSet<T> intersection(LinkedSet<T> otherSet) {
		if (theSet.equals(otherSet)){
			return otherSet;
		} else {
			LinkedSet<T> intersectionSet = new LinkedSet<T>();
			Iterator<T> i = theSet.iterator();
			while (i.hasNext()){
				if(otherSet.isMember(i.peek())){
					intersectionSet.add(i.peek());
				}
				i.next();
			}
			return intersectionSet;
		}
	}

	/**
	 * Returns a new iterator
	 * 
	 * @return		A new iterator
	 * @complexity	Best and worst case: O(1)
	 */
	@Override
	public Iterator<T> iterator() {
		return new MyIterator();
	}

	/**
	 * Determines whether this set is the same as another set
	 * 
	 * @param		otherO The other set
	 * @pre			otherO can be cast to a LinkedSet without causing issues
	 * @returns		Whether the other set is the same as this one
	 * @complexity	Best and worst case: O(I)
	 * 				where I is the complexity of finding the intersection set of thisSet and otherO
	 * 				Note that this assumes the getClass method and the casting operations are
	 * 				constant complexity.
	 */
	public boolean equals(Object otherO){
		if(otherO == null || getClass() != otherO.getClass()) {
			return false;
		}
		
		LinkedSet<T> otherSet = (LinkedSet<T>) otherO;
		LinkedSet<T> intersectionSet = (LinkedSet<T>) intersection(otherSet);
		
		return (cardinality() == intersectionSet.cardinality() &&
				otherSet.cardinality() == intersectionSet.cardinality());
		
	}
	
	/**
	 * Prints the contents of the set
	 * 
	 * @return		null
	 * @output		The contents of the set
	 * @complexity	Best and worst case: O(N)
	 * 				where N is the size of the set
	 */
	public String toString(){
		Iterator<T> i = theSet.iterator();
		while(i.hasNext()){
			System.out.println(i.peek());
			i.next();
		}
		return null;
	}
}
